/**
 * 二维平面给定横平竖直的矩形，问是否能满足如下条件之一：
 * 1. 画两条水平线，不穿过任意矩形内部（可以贴边），将平面分为三个部分，每个部分均存在矩形
 * 2. 画两条竖直线，不穿过任意矩形内部（可以贴边），将平面分为三个部分，每个部分均存在矩形
 * 
 * 维护一个range的数据结构，允许插入操作。每次插入操作，需要合并相交的区间。
 * 最多插入一次，删除两次，定位是log的。因此插入操作可以在log时间内完成
 * 完成以后，如果数据结构中还存在3个及其以上的元素即可。
 * 注意到点的特性，因此要用左闭右开模式。即假设矩形的左右x坐标是[3,6]，
 * 则应该插入[3, 6-1]。
 */
struct RangeTree{ // 区间集合

using key_t = pair<int, int>;
using value_t = int;

///pbds不支持范围erase操作
std::map<key_t, value_t> shu;

RangeTree():shu(){init();}

void init(){
    shu.clear();
    /// 插入哨兵
    shu.insert({{ninf(), ninf()}, value_zero()});
    shu.insert({{inf(), inf()}, value_zero()});
}

static int inf(){
    static const int INF = 0x7F7FFFFF;
    return INF;
}

static int ninf(){return -inf();}

static value_t value_zero(){
    static const value_t VALUE_ZERO = 0;
    return VALUE_ZERO;
}

/// 插入区间[a, b]，如有必要会有合并操作
void insert(int a, int b, const value_t & v = value_zero()){
    assert(not shu.empty() and a <= b);

    key_t toInsert;
    

    /// 找到a前面一个
    auto sit = shu.lower_bound({a, inf()});
    assert(sit != shu.begin() and sit != shu.end() and sit->first.first > a);
    --sit;

    decltype(sit) toDelBegin, toDelEnd;

    if(sit->first.second >= a){
        toInsert.first = sit->first.first;
        toDelBegin = sit;
    }else{
        toInsert.first = a;
        toDelBegin = ++sit;
    }

    auto eit = shu.lower_bound({b, inf()});
    assert(eit != shu.begin() and eit != shu.end() and eit->first.first > b);

    if(eit->first.first == b){
        toInsert.second = eit->first.second;
        toDelEnd = ++eit;
    }else{
        toDelEnd = eit;
        --eit;
        toInsert.second = max(eit->first.second, b);
    }

    if(toDelBegin != toDelEnd) {
        shu.erase(toDelBegin, toDelEnd);
    }
    shu.insert({toInsert, v});
    return;
}

};

class Solution {

using vi = vector<int>;
RangeTree st;
vi W;

public:
    bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
        for(const vi & v : rectangles){
            W.emplace_back(v[0]);
            W.emplace_back(v[2]);
        }        
        if(proc()) return true;
        
        W.clear();
        for(const vi & v : rectangles){
            W.emplace_back(v[1]);
            W.emplace_back(v[3]);
        }  
        if(proc()) return true;
        return false;
    }

    bool proc(){
        vi w(W.begin(), W.end());
        w.emplace_back(-1);
        sort(w.begin(), w.end());
        w.erase(unique(w.begin(), w.end()), w.end());

        int n = w.size();
        st.init();
        for(int i=0;i<W.size();i+=2){
            int a = lower_bound(w.begin(), w.end(), W[i]) - w.begin();
            int b = lower_bound(w.begin(), w.end(), W[i + 1]) - w.begin();
            st.insert(a, b - 1, 1);
        }
        return st.shu.size() >= 5;
    }
};